package com.zhu.exercise.sort;

import org.junit.Test;

public class QuickSort {

    @Test
    public void test(){
        int arr[] = new int[]{12,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};
        int len = arr.length-1;
        arr=qsort(arr,0,len);
        for (int i:arr) {
            System.out.print(i+"\t");
        }

    }

    public static int[] qsort2(int arr[],int start,int end){
        if (start >= end) {//如果左边的索引大于等于右边的索引说明整理完毕
            System.out.println(start);
            System.out.println(end);
            //return arr;
        }
        //从前面取基准第一次就要从后面遍历
        int pivot = arr[start];
        int i =start;
        int j =end;

        //遍历直至两个游标一致
        while(i<j){
            //找第一个小数
            while(i<j&&arr[j]>=pivot){
                j--;
            }
            //小数换到开头
            arr[i]=arr[j];

            //找第一个大数
            while(i<j&&arr[i]<=pivot){
                i++;
            }
            //大数换到后面
            arr[j]=arr[i];
        }
        //一轮遍历以后,j处于分界点，填入基准值
        arr[j]=pivot;
        qsort2(arr,start,j-1);
        qsort2(arr,j+1,end);

        return arr;
    }

    public static int[] qsort(int arr[],int start,int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;

        //遍历数组（这种写法其实每次arr[i] 和arr[j] 必然有一个等于pivot）
        while (i<j) {
            //从后向前遍历，找到第一个大于基准的数(第一次遍历以后arr[j]必然=基准，因此第二次遍历arr[j]>pivot必然为假)
            while ((i<j)&&(arr[j]>pivot)) {
                j--;
            }
            //从前向后遍历，找到第一个小于基准的数，（因为基准为第一个数，因此第一次i肯定为0）
            while ((i<j)&&(arr[i]<pivot)) {
                i++;
            }
            //相同交换没有意义，增加i坐标，开启新的遍历
            if ((arr[i]==arr[j])&&(i<j)) {
                i++;
            } else {
                //不相同则交换位置
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            System.out.println("----------------------------");
            System.out.println(i);
            System.out.println(j);
        }
        //这种方法要判断区间是否在数组边界 i j其实相等的
        if (i-1>start) arr=qsort(arr,start,i-1);
        if (j+1<end) arr=qsort(arr,j+1,end);
        return (arr);
    }
}
